\documentclass[a4paper,12pt]{article} 
\usepackage[italian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath,stmaryrd,amsthm}
\usepackage{graphicx}
\usepackage{multirow}
%\usepackage{url}
\usepackage{textcomp}
\usepackage{booktabs}
%\usepackage{glossary}
\usepackage{setspace}
\usepackage{listings}
\usepackage{courier}
\usepackage[usenames,dvipsnames]{color}
\usepackage{hyperref}
\usepackage{algorithm}
\usepackage{algpseudocode}


%enable subsection number
\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{4}

\lstset{
%basicstyle=\small,
basicstyle=\footnotesize\ttfamily,
commentstyle=\textit,
showstringspaces=false,
frame=trbl,
linewidth=350px
}

\addto\captionsitalian{%
\renewcommand{\lstlistingname}{Tabella}}

\floatname{algorithm}{Algoritmo}

 \begin{document}

\begin{center}
\normalsize
\includegraphics[width=.35\columnwidth]{immagini/unipd_logo} \\ \bigskip
\rmfamily\normalfont{Relazione di Progetto} \\ \bigskip
\begingroup
\rmfamily\normalfont\color{Maroon}{\Large Fuzzy-CSP Generator\&Solver} \\ \bigskip
\endgroup

\begin{tabular}{cc}
{\Large Federico Serafini}          & {\Large Lorenzo Tessari} \\
federico.serafini@studenti.unipd.it & lorenzo.tessari@studenti.unipd.it \\
Matricola: 1013995                  & Matricola: 1014342
\end{tabular}

\end{center}

\bigskip


\section*{Abstract}

Lo scopo di questo progetto riguarda lo sviluppo di un programma in grado di generare dei csp fuzzy casuali e determinarne in seguito la soddisfacibilità attraverso l'algoritmo di Arc-Consistency AC2001. Poiché quest'algoritmo è stato creato per csp classici, si è reso necessario un riadattamento alla tipologia fuzzy, prendendo spunto dalla pubblicazione ``Node and Arc Consistency in Weighted CSP'' di Javier Larrosa e dal capitolo 9 del testo ``Handbook of Constraint Programming'' di P. Meseguer, F. Rossi, T. Schiex.

\newpage
\section{Introduzione}

La programmazione a vincoli, detta anche programmazione con vincoli o constraint è un paradigma di programmazione dove le relazioni fra variabili possono essere dichiarate in forma di vincoli. I vincoli differiscono dalle primitive normalmente definite dagli altri linguaggi di programmazione per il fatto che non specificano azioni singole da eseguire passo-passo, ma piuttosto si limitano a specificare le proprietà di cui deve essere dotata la soluzione da trovare. I vincoli usati possono essere di vari tipi: quelli basati sul cosiddetto problema di soddisfacimento di vincoli (Constraint satisfaction problem o CSP), quelli risolvibili mediante l'algoritmo del Simplesso (Simplex Algorithm) ed altri. I vincoli da applicare possono essere forniti embedded nel linguaggio di programmazione, oppure in librerie separate.

La programmazione a vincoli iniziò come programmazione logica a vincoli, introducendo vincoli integrati in un programma di tipo logico. Questa variante della programmazione logica fu opera di Jaffar e Lassez, che, nel 1987, svilupparono una classe di vincoli specificatamente progettata per essere usata nel linguaggio Prolog II. La prime implementazioni di programmazione logica a vincoli furono Prolog III, CLP(R), e CHIP. Attualmente esistono molti interpreti per programmi logici a vincoli, come per esempio GNU Prolog.

Nei linguaggi imperativi, tuttavia, i vincoli sono implementati principalmente mediante i cosiddetti constraint solving toolkits, che sono librerie separate, fornite insieme al linguaggio. ILOG CP Optimizer, è un esempio è di queste librerie per C++, Java e .NET.

\subsection{CSP}

Molti problemi nell'ambito dell'Intelligenza Artificiale sono classificabili come Problemi di Soddisfacimento di Vincoli \textit{(Constraint Satisfaction Problem o CSP)}; fra questi citiamo problemi di complessità combinatoria, di allocazione di risorse, pianificazione e ragionamento temporale. Questi problemi possono essere risolti efficientemente attraverso tecniche ben note di risoluzione di CSP.

Formalmente, un CSP può essere definito su un insieme finito di variabili $(X_1, X_2, \dots, X_n)$ i cui valori appartengono a domini finiti di definizione $(D_1, D_2, \dots, D_n)$ e su un insieme di vincoli. Un vincolo su un insieme di variabili è una restrizione dei valori che le variabili possono assumere simultaneamente. Concettualmente, un vincolo può essere visto come un insieme che contiene tutti i valori che le variabili possono assumere contemporaneamente: un vincolo tra $k$ variabili $c(X_{i_1},X_{i_2},\dots,X_{i_k})$ è un sottoinsieme del prodotto cartesiano dei domini delle variabili coinvolte $D_{i_1},D_{i_2},\dots,D_{i_k}$ che specifica quali valori delle variabili sono compatibili con le altre. Questo insieme può essere rappresentato in molti modi, per esempio per mezzo di matrici, equazioni, disuguaglianze o relazioni. Una soluzione ad un CSP è un assegnamento di valori alle variabili che soddisfi tutti i vincoli.

Si cita brevemente come esempio noto il problema delle 8 regine, ovvero disporre su una scacchiera 8 regine in modo che non si attachino a vicenda.

\subsubsection{Fuzzy CSP}
In molti casi reali può essere utile avere un modello in cui è possibile associare ai vincoli dei gradi di libertà, o meglio, dei gradi di preferenza, e non solamente la proprietà vincolo rispettato/violato.
Infatti in questi casi i CSP classici risultano essere troppo restrittivi, poiché non sono in grado di rappresentare delle preferenze associate ai vincoli; è principalmente per questo motivo che sono stati introdotti i \textit{CSP fuzzy}.

Questi si basano sulla teoria degli insiemi fuzzy; i vincoli fuzzy rappresentano la prima estensione della nozione classica di vincoli, in grado di rappresentare esplicitamente delle preferenze.
Un vincolo classico può essere visto come un insieme di valori delle variabili del problema, ovvero di valori consentiti per ottenere una soluzione del problema.
Nel framework fuzzy, un vincolo non è più un insieme di valori, ma è invece un insieme \textit{fuzzy} di valori: per ogni assegnamento delle variabili è possibile definire in che misura è presente nell'insieme; in altre parole, qual è il grado di appartenenza (\textit{preferenza}) dell'assegnamento in esame.

Con questo modello quindi è possibile rappresentare delle combinazioni di valori delle variabili che fanno parte di un vincolo, ammesse parzialmente.
La \textit{funzione di appartenenza} $\mu_E$ di un insieme fuzzy $E$ associa un numero reale compreso tra 0 e 1 per ogni possibile elemento di $E$.
Quindi, se consideriamo ogni vincolo come insieme fuzzy, possiamo associare ad ogni assegnamento un valore reale, compreso tra 0 ed 1, dato dalla funzione di appartenenza.
In questo contesto un CSP classico può essere rappresentato permettendo soltanto, per la funzione di appartenenza, il valore 1 (vincolo rispettato) e il valore 0 (vincolo violato).

Come per i CSP classici, anche per i CSP fuzzy una soluzione è ottenuta quando tutti i vincoli sono soddisfatti (preferenza maggiore di 0), quindi quando la preferenza associata ad un assegnamento completo delle variabili è maggiore di 0.
Il modo con cui si combinano tra loro più assegnamenti parziali è quello di associare, alla tupla risultante, la minima preferenza degli assegnamenti che la compongono.
La \textit{soluzione ottima} del problema, poiché valori di preferenza maggiori sono da preferire, è data dall'assegnamento globale che massimizza le preferenze minime delle sottotuple che lo compongono.
Il processo di ottimizzazione consiste quindi nel massimizzare il valore della tupla con preferenza minima consentita.

\subsection{Arc-Consistency}

Una variabile di un problema di soddisfacimento vincoli è consistente sugli archi con un altra se ciascuno dei suoi valori ammissibili è consistente con un valore ammissibile della seconda variabile. Formalmente, una variabile $x_i$ è consistente sugli archi con un altra variabile $x_j$ se, per ogni valore $a$ nel dominio di $x_i$ esiste un valore $b$ nel dominio di $x_j$ tale che $(a, b)$ soddisfa il vincolo binario tra $x_i$ e $x_j$. Un problema è consistente sugli archi se ogni variabile è consistente sugli archi con qualunque altra.

Si consideri ad esempio il vincolo $x < y$ dove le variabili variano nel dominio $\{1,3\}$. Poiché x non può mai assumere valore 3, non esiste un arco da 3 a un valore di y, per cui è possibile rimuovere tale valore. Allo stesso modo y non può mai essere 1, quindi non esistono archi e tale vincolo può essere rimosso.

Se una variabile non è consistente sugli archi con un altra, può diventarlo rimuovendo alcuni valori dal suo dominio. Questa è la forma di propagazione sui vincoli che impone la consistenza sugli archi: si toglie, dal dominio della variabile, ogni valore che non corrisponde ad un valore dell'altra variabile. Questa trasformazione mantiene la soluzione del problema, poiché i valori rimossi non fanno parte di alcuna soluzione.

La propagazione sui vincoli può rendere l'intero problema consistente sugli archi ripetendo queste rimozioni per tutte le coppie di variabili. Durante questo processo potrebbe essere necessario prendere in considerazione una coppia di variabili più di una volta. Infatti, eliminando i valori dal dominio di una variabile, altre variabili potrebbero non essere più consistenti sugli archi con quest'ultima. Per esempio, se è $x_3$ è consistente sugli archi con $x_2$ ma l'algoritmo riduce il dominio di $x_2$, la consistenza di $x_3$ con $x_2$ non è più garantita e deve quindi essere eseguita di nuovo.

\subsubsection{Fuzzy Arc-Consistency}

La \textit{fuzzy arc-consistency} è simile alla procedura di arc-consistency descritta nella sezione precedente, tuttavia nel caso dei CSP fuzzy dobbiamo tenere in considerazione anche le preferenze associate agli assegnamenti.

Utilizzando l'operatore di combinazione dei vincoli fuzzy, che seleziona la preferenza minima dell'assegnamento (indicato col simbolo $\otimes$), la consistenza su un generico arco $(x_i,x_j)$ è ottenuta nel seguente modo:
\[
c_{x_i}:=(c_{x_i} \otimes c_{x_ix_j} \otimes c_{x_j})|_{x_i}
\]
dove $|_{x_i}$ è l'operatore di proiezione, definito come
\begin{align*}
se & \quad c=<f,con> \quad allora \quad c|_l = <f',l \cap con> \\
con & \quad f'(t') = max(f(t)) \quad \forall t \quad t.c. \quad t|_{l \cap con} = t'
\end{align*}

La procedura di consistenza viene applicata ad ogni arco del CSP finché non si raggiunge la stabilità, ovvero quando tutti i vincoli unari $C_{x_i}$ sono aggiornati.

Quando un valore $b \in D_i$ - con $D_i$ dominio della variabile $x_i$ - ha preferenza 0 (vincolo unario violato) allora il valore $b$ viene rimosso dal dominio $D_i$.
Può capitare quindi che durante il processo di arc-consistency il dominio di una variabile $x_i$ venga svuotato, poiché tutti i valori del dominio $D_{x_i}$ hanno preferenza 0.
Quando ciò si verifica il problema non è consistente sugli archi e non ha dunque soluzione.

\subsubsection{FuzzyAC2001}
\label{sec: FuzzyAC2001}
Nella letteratura scientifica sono stati presentati svariati algoritmi che realizzano la consistenza sugli archi su CSP (e.g. \textit{AC1, AC3, AC4, AC2001}).
Tuttavia, l'introduzione delle preferenze sui vincoli richiede alcune modifiche agli algoritmi di arc-consistency sviluppati per i CSP classici e in alcuni casi non è proprio possibile riadattarli al caso fuzzy.

L'algoritmo FuzzyAC2001, illustrato nel listato \ref{alg: Funzione FuzzyAC2001}, realizza la consistenza sugli archi su CSP fuzzy.
Si basa su AC2001 (Bessiere \& Regin 2001), un semplice ed efficiente algoritmo di AC per CSP.

La consistenza sugli archi può essere ottenuta applicando due semplici operazioni: la rimozione di valori inconsistenti dal dominio delle variabili (con preferenza 0); la ricerca di un supporto per ogni valore del dominio delle variabili rispetto ad ogni vincolo, ovvero: date due variabili $i$ e $j$, il supporto di $a \in D_i$ rispetto a $C_{ij}$ è $argmax_{b \in D_j}\{C_{ij}(a,b)\}$.

$FuzzyAC2001$ richiede una struttura dati $S(i,a,j)$ che memorizza una tripla $(val,pref,valid)$ per $(i,a)$ rispetto al vincolo $C_{ij}$: $val$ è il valore supporto, definito nel paragrafo precedente; $pref$ è la preferenza associata al supporto; $valid$ indica se il supporto è da considerarsi valido.
Inizialmente tutti i supporti $S(i,a,j)$ sono inizializzati a $(Nil,0,false)$, che significa che non si conosce ancora il supporto per $a$.

L'algoritmo utilizza due funzioni.
$PruneVar(i)$ rimuove tutti i valori inconsistenti (con preferenza 0) dal dominio $D_i$ e restituisce $true$ se il dominio viene modificato.
La $FindSupports(i,j)$ proietta il vincolo $C_{ij}$ su $C_i$, o, in altri termini, cerca un supporto per ogni valore in $D_i$ che non ne ha ancora uno o che sia stato invalidato.
La funzione principale $FuzzyAC2001$ ha la tipica struttura degli algoritmi AC.
$Q$ è un insieme che contiene tutte le variabili il cui dominio è stato modificato, o rimuovendo un valore o modificando la preferenza associata ad un valore; è possibile quindi che ora le variabili ad essa adiacenti contengano dei valori non supportati nel proprio dominio.
$Q$ è inizializzata con tutte le variabili (linea 34), poiché ogni variabile deve cercare inizialmente un supporto per ciascun valore del proprio dominio rispetto ad ogni vincolo in cui è coinvolta.
Il ciclo principale (linea 35) itera finché c'è qualche elemento in $Q$, oppure il dominio di qualche variabile è diventato vuoto.
Una variabile $j$ viene estratta dall'insieme $Q$ e per ciascuna variabile a cui è legata da un vincolo vengono cercati dei supporti per $D_i$ (linea 38).
Se la preferenza di qualche valore del dominio $D_i$ viene modificata, allora $i$ viene aggiunta all'insieme $Q$, poiché delle variabili connesse ad $i$ potrebbero avere dei supporti per alcuni valori la cui preferenza è cambiata.
I valori inconsistenti nel dominio $D_i$ vengono rimossi (linea 41) e se questo cambia allora la variabile $i$ va aggiunta nuovamente all'insieme $Q$.
Infine, viene controllato se il dominio $D_i$ è diventato vuoto, nel qual caso il ciclo termina, così come l'algoritmo.

Una nota riguardo la funzione $FindSupports(i,j)$: dopo aver trovato il valore che massimizza la preferenza per $(i,a,j)$ (linea 5) ed aver calcolato il minimo tra la preferenza ad esso associata e $C_i(a)$ (linea 6) viene aggiornato il valore sia il supporto $S(i,a,j)$ che quello della preferenza $C_i(a)$; inoltre, per ogni valore $b \in D_j$, se la preferenza $C_{ij}(a,b)$ è maggiore della preferenza del supporto $\alpha$ viene aggiornata al valore $\alpha$ (linea 11), poiché l'operatore di combinazione di vincoli prevede di utilizzare la preferenza minima dei vincoli combinati.
Alla linea 12 viene controllato se il supporto inverso $S(j,v,i)$ ha preferenza maggiore di $\alpha$, nel qual caso, per le stesse ragioni esposte prima, il supporto $S(j,v,i)$ deve essere invalidato (linea 13).

\begin{algorithm}
\caption{Funzione FindSupports}
\label{alg: Funzione FindSupports}
\begin{algorithmic}[1]
\Function{FindSupports}{$i,j$}
	\State \texttt{change} $\gets$ \texttt{\textbf{false}}
	\ForAll{$a \in D_i$}
		\If{$\neg S(i,a,j).\mathtt{valid} \lor S(i,a,j).\mathtt{val} \notin D_j$}
			\State $v \gets \mathrm{argmax}_{b \in D_j} \{C_{ij}(a,b)\}$
			\State $\alpha \gets \min(C_i,C_{ij}(a,v))$
			\State $S(i,a,j) \gets (v,\alpha,$\texttt{\textbf{true}}$)$
			\State $C_i(a) \gets \alpha$
			\ForAll{$b \in D_j$}
				\If{$C_{ij}(a,b) > \alpha$}
					\State $C_{ij}(a,b) \gets \alpha$
					\If{$S(j,v,i).\mathtt{val} = a \land S(j,v,i).\mathtt{pref} > \alpha$}
						\State $S(j,v,i).\mathtt{valid} \gets$ \texttt{\textbf{false}}
						\State \texttt{change} $\gets$ \texttt{\textbf{true}}
					\EndIf
				\EndIf
			\EndFor
		\EndIf
	\EndFor
	\State \textbf{return} \texttt{change}
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Funzione PruneVar}
\label{alg: Funzione PruneVar}
\begin{algorithmic}[1]
\addtocounter{ALG@line}{21}
\Function{PruneVar}{$i$}
	\State \texttt{change} $\gets$ \texttt{\textbf{false}}
	\ForAll{$a \in D_i$}
		\If{$C_i(a) = \top$} \Comment{$\top$ è la preferenza minima}
			\State $D_i \gets D_i - \{a\}$
			\State \texttt{change} $\gets$ \texttt{\textbf{true}}
		\EndIf
	\EndFor
	\State \textbf{return} \texttt{change}
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Funzione FuzzyAC2001}
\label{alg: Funzione FuzzyAC2001}
\begin{algorithmic}[1]
\addtocounter{ALG@line}{31}
\Function{FuzzyAC2001}{$\mathcal{X,D,C}$}
	\State \texttt{has\_solution} $\gets$ \texttt{\textbf{true}}
	\State $Q := {1,2,\dots,n}$
	\While{\texttt{has\_solution} $\land Q \neq \emptyset$}
		\State $j \gets pop(Q)$
		\ForAll{$C_{ij} \in \mathcal{C}$}
			\If{$FindSupports(i,j)$}
				\State $Q \gets Q \cup \{i\}$
			\EndIf
			\If{$PruneVar(i)$}
				\State $Q \gets Q \cup \{i\}$
			\EndIf
			\If{$D_i = \emptyset$}
				\State \texttt{has\_solution} $\gets$ \texttt{\textbf{false}}
			\EndIf
		\EndFor
	\EndWhile
	\State \textbf{return} \texttt{has\_solution}
\EndFunction
\end{algorithmic}
\end{algorithm}

\newpage
$\:$
\newpage
\section{Implementazione}

L'ambiente di sviluppo scelto è stato l'$SDK\; QT\; 4.7$ con $QT\; Creator\; 2.4$ come editor. Questo Framework multipiattaforma permette in maniera semplice di avere tutto il necessario per costruire un'interfaccia grafica su cui appoggiare il nostro progetto; il linguaggio utilizzato è il c++, il quale permette di avere una migliore performance nell'esecuzione. Il codice binario fornito è per Win32, ma dato il codice sorgente è possibile compilarlo per qualsiasi piattaforma supportata dalle $QT$ (Win, Linux, Mac e con poche modifiche anche per Mobile: Harmattan, Symbian, ...).

\subsection{Classi}

Il progetto è suddiviso principalmente in due Layer: abbiamo l'interfaccia grafica ed il package per generazione e risoluzione di CSP:

\begin{itemize}
\item FuzzyCSPSolver Package\begin{itemize}
\item BinaryCostraint
\item FCSP
\item Solver
\item Variable

\end{itemize}
\item GData
\item MainWindow
\item WGraph

\end{itemize}

\subsection{Fuzzy CSP}

Il nocciolo fondamentale, nonché punto di partenza, del package FuzzyCSPSolver riguarda l'implementazione del CSP fuzzy.
Questa è stata ottenuta suddividendo il CSP nei suoi elementi di base\footnote{Si ricordi che un CSP viene genericamente rappresentato mediante una tripla $\left\langle X,D,C \right\rangle$ dove $X$ è un insieme di variabili, $D$ è un dominio di valori e $C$ è un insieme di vincoli.}: le variabili ed i i vincoli.
Ogni variabile memorizza l'insieme dei valori permessi, associando a ciascuno di essi una preferenza: in questo modo si è riunito all'interno delle variabili vincoli unari e e dominio dei valori.
I vincoli, per scelta progettuale, sono limitati al caso binario; per ogni assegnamento delle due variabili coinvolte nel vincolo viene associata una preferenza.

\subsubsection{Classe Variable}
La classe Variable implementa un nodo del CSP.
Ad ogni oggetto Variable viene associato:
\begin{itemize}
\item un id, utilizzato per identificare univocamente la variabile nel CSP;
\item una stringa per memorizzare il nome del nodo;
\item una struttura \texttt{map}, che associa una preferenza per ogni valore presente nel dominio della variabile;
\item una lista di puntatori ai nodi adiacenti, ovvero ai nodi con cui è coinvolta in un vincolo.
\end{itemize}

\subsubsection{Classe BinaryConstraint}
La classe BinaryConstraint implementa un vincolo tra due variabili del CSP.
Un oggetto di questa classe ha due puntatori agli oggetti Variable coinvolti nel vincolo, nonché una matrice di preferenze, dove vengono memorizzate le preferenze di ciascuna combinazione dei valori presenti nel dominio delle due variabili\footnote{Non necessariamente vengono memorizzate tutte le preferenze: si assume infatti che se una combinazione di valori non è presente nella matrice allora questa ha preferenza 0 (vincolo violato).}.

\subsubsection{Classe FCSP}
Questa classe implementa il Fuzzy CSP vero e proprio, mantenendo una lista di oggetti Variable e una lista di oggetti BinaryConstraint.

Possiede tutti i metodi necessari per gestire le variabili del CSP ed i vincoli ad esse associati, in modo tale da mantenere la struttura del CSP consistente.

\subsection{CSP Random}
Al fine di testare le prestazioni dell'algoritmo di arc-consistency implementato è stato implementato un metodo, all'interno della classe FCSP, per generare casualmente dei CSP.

Ogni CSP generato casualmente è caratterizzato da una tupla $(k,n,d,p_1,p_2)$:
\begin{itemize}
\item $k=$ arietà dei vincoli (tutti con la stessa arietà, che nel nostro caso è pari a 2);
\item $n=$ numeri di variabili;
\item $d=$ grandezza dei domini (uguali per tutte le variabili);
\item $p_1=$ densità del grafo dei vincoli (quanti vincoli ci sono rispetto al numero massimo totale);
\item $p_2=$ strettezza (tightness) dei vincoli (quante tuple sono proibite dai vincoli).
\end{itemize}

\subsubsection{Metodo GenCsp}
Il metodo GenCsp della classe FCSP si occupa della generazione di un CSP casuale a partire dai parametri forniti in ingresso, corrispondenti alla tupla $(k=2,n,d,p_1,p_2)$\footnote{Nel nostro caso $p_1$ e $p_2$ si riferiscono a delle proporzioni.}.

Questo metodo si avvale di altri due metodi:
\begin{itemize}
\item GenVariablePrefs: genera una lista di preferenze per una variabile avendo come input la cardinalità del dominio della variabile e la stretteza dei vincoli ($p_2$);
\item GenConstraintPrefs: genera una lista di preferenze per un vincolo avendo come input  le cardinalità dei domini delle variabili coinvolte nel vincolo e la stretteza dei vincoli ($p_2$).
\end{itemize}

\subsection{Solver}
Il solver si occupa di verificare se un dato CSP fuzzy ha soluzione o meno.
Poiché ci siamo limitati a considerare CSP fuzzy con vincoli di arietà massima pari a 2, l'applicazione dell'algoritmo di consistenza sugli archi è sufficiente a stabilire se il problema ha o no soluzione; infatti è sufficiente verificare se durante l'applicazione dell'algoritmo il dominio di qualche variabile diventa vuota.

\subsubsection{Classe Solver}
La classe Solver implementa l'algoritmo di arc-consistency esposto nel capitolo \ref{sec: FuzzyAC2001}, attraverso 3 metodi, corrispondenti alle 3 funzioni illustrate nel capitolo citato.
Inoltre, per memorizzare i supporti $S(i,a,j)$ viene utilizzata una matrice 3-dimensionale.

La funzione $FuzzyAC2001$ prende in input un puntatore ad un CSP fuzzy e restituisce un valore booleano \texttt{true} se il problema ha soluzione \texttt{false} altrimenti.
Poiché nei nostri test siamo principalmente interessati a verificare la soddisfacibilità di un problema, è possibile passare a questa funzione un parametro booleano attraverso il quale selezionare una procedura di arc-consistency parziale.
Quando la preferenza associata ad un valore di una variabile viene ridotta, ma rimane maggiore di 0, potrebbe essere necessario propagare tale modifica a preferenze di valori di variabili adiacenti - quello che l'algoritmo ottiene invalidando un supporto (linea 13) - quindi la variabile viene reinserita nell'insieme delle variabili per cui cercare supporti.
L'AC parziale non esegue questo tipo di controllo, di conseguenza le uniche variabili ad essere reinserite nell'insieme $Q$ sono solo quelle a cui è stato rimosso un valore dal dominio (linee 41-43), e questo è sufficiente a verificare se il problema ha soluzione.
L'arc-consistency parziale è ovviamente più veloce di quella completa, ed è utile per conoscere la soddisfacibilità di un problema; tuttavia, poiché viene tralasciata la propagazione di alcune preferenze, al termine dell'esecuzione è possibile ottenere un problema non consistente sugli archi, in cui cioè le preferenze proiettate sui vincoli unari non sono quelle minime.

\subsection{GUI}

L'interfaccia è lo strato a diretto contatto con l'utente, deve essere semplice, intuitiva e fornire a colpo d'occhio tutto il necessario per lavorare. Inoltre deve controllare che gli input dati dall'utente siano consistenti col problema ed in caso negativo indirizzarlo verso la correzione. Fornisce inoltre ad esecuzione completata un grafico sull'andamento della risoluzione del problema a seconda dei dati di partenza forniti.

\subsubsection{Classe GData}

La classe GData si occupa di mantenere i dati del problema ed i risultati dati dal solver per poi plottare a video il grafico.

\subsubsection{Classe MainWindow}

La classe MainWindow si occupa di gestire l'iterazione con l'utente, fornendogli una schermata semplice ed immediata per inserire i dati relativi al problema ed usando i relativi controlli perché i dati siano consistenti, notificando eventuali errori.

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.5]{immagini/scsp.png}
\caption{Schermata della GUI}
\label{fig: Schermata della GUI}
\end{figure}

Nel menù \textit{Options} si può selezionare la modalità parziale o completa dell'algoritmo AC2001 descritto nel capitolo 2.4.

Durante l'esecuzione viene fornita la possibilità, qualora si ritenesse necessario, di interrompere il processo; in tal caso non verrà ovviamente visualizzato nessun grafico riassuntivo.

\subsubsection{Classe WGraph}

La classe WGraph si occupa di visualizzare il grafico risultante dalla risoluzione del csp nelle varie istanze, mostrando l'andamento sia per il tempo di calcolo (medio) di ogni iterazione sia sulla percentuale di FSCP effettivamente risolvibili.

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.2]{immagini/graph.png}
\caption{Schermata del grafico finale}
\label{fig: Schermata del grafico finale}
\end{figure}

\newpage
\section{Utilizzo del programma}

Il programma fornisce principalmente due tipologie di approccio:
\begin{itemize}
\item approccio statistico
\item approccio fisso

\end{itemize}

Nel primo caso si inseriscono valori minimi/massimi nei rispettivi campi dati del gruppo $Soft\text{-}CSP\;setup$ ed un buon numero di istanze nel gruppo $Batch\;mode$; in questo modo verrà fornita una media sui risultati complessivi di problemi.\\

Nel secondo, invece, si inserisce lo stesso valore nei campi dati del gruppo $Soft\text{-}CSP\;setup$ ed un numero variabile, da 1 in su, nel campo del numero di istanze del gruppo $Batch\;mode$; essendo la generazione del csp casuale, ma partendo sempre dagli stessi parametri, può essere utile utilizzare diverse istanze per avere una stima migliore sulla data configurazione.\\

In entrambi i casi è possibile utilizzare il $batch\;mode$ settando un numero congruo per il campo incremento ed ottenere così un grafico che mostra l'andamento in tempo calcolo e percentuale problemi risolti.\\

Nel menù $options$, infine, è possibile selezionare se si vuole utilizzare la versione parziale o completa dell'AC2001 implementato; si noti che la versione completa richiede sensibilmente più tempo. Per eventuali chiarimenti sulle due modalità si rimanda al capitolo 2.4.

\newpage
\subsection{Esecuzione}

Dopo aver inserito i parametri desiderati premendo il pulsante \textit{Start} parte l'esecuzione, mostrando una barra di avanzamento e un messaggio di status che quantifica il numero di iterazioni fatte sul totale. In qualsiasi momento è possibile premere il pulsante \textit{Stop} per interrompere il processo (figura \ref{fig: Programma in esecuzione}).

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.5]{immagini/scsp_esec.png}
\caption{Programma in esecuzione}
\label{fig: Programma in esecuzione}
\end{figure}

Nel caso il valore del campo \textit{incremento} fosse 0, non essendo necessario plottare un grafico, viene dato un messaggio riassuntivo del risultato indicando il tempo medio di esecuzione del solver e quanti problemi sul totale erano risolvibili (figura \ref{fig: Risultato senza incrementi}).

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.5]{immagini/scsp_noInc.png}
\caption{Risultato senza incrementi}
\label{fig: Risultato senza incrementi}
\end{figure}

\subsubsection{Grafico}

Se è stato fornito un valore maggiore di 0 nel campo $incremento$, viene plottato a video il grafico. In base alla variabile selezionata nel gruppo $Batch$ $mode$, si può vedere l'andamento del tempo calcolo medio e della percentuale di csp risolti all'aumentare del suo valore.

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.2]{immagini/graph.png}
\caption{Schermata del grafico finale (2)}
\label{fig: Schermata del grafico finale (2)}
\end{figure}
\newpage
Come da Legenda abbiamo in blu con pallini rossi in corrispondenza dei valori trovati il tempo di calcolo ed in verde l'andamento percentuale di csp risolti; si fa notare che l'apice del grafico corrisponde al 100\% di csp risolti ed il fondo lo 0\%.

\subsection{Considerazioni Finali}

%TODO integrazione fede

I risultati forniti dai grafici ci permettono di fare alcune valutazioni all'aumentare di valori specifici nella generazione dei csp; i parametri di riferimento generali per la generazione dei csp (quindi escludendo i casi di incremento che verranno specificati man mano) sono i seguenti:
\begin{itemize}
\item numero di variabili: 80
\item grandezza dei domini: 5
\item densità del grafo: 0.8
\item tightness: 0.5
\item istanze per iterazione: 10
\item Arc-Consistency parziale\\
\end{itemize}

Il primo caso in esame è l'aumento del numero di variabili (figura \ref{fig: Incremento del numero di variabili}): siamo partiti da un valore minimo di 10 per arrivare a 150 con un incremento di 10 ad iterazione; come si può notare dal grafico risultante, il tempo medio di calcolo cresce esponenzialmente con il numero di variabili che l'algoritmo deve considerare, trovando solo molto dopo se il csp è risolvibile o meno; chiaramente all'aumentare delle variabili è sempre più difficile che il csp abbia soluzione, fino a non averne più (per i parametri di input dati) per un numero di variabili superiore a 60.
\vspace{1cm}

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.3]{immagini/graph_time-numvar.png}
\caption{Incremento del numero di variabili}
\label{fig: Incremento del numero di variabili}
\end{figure}

Nel caso dei domini con incremento di 5 nell'intervallo [5,50] (figura \ref{fig: Incremento della dimensione del dominio}), invece, il tempo di calcolo aumenta con l'aumentare dei valori da controllare ma è anche più facile trovare una soluzione che soddisfi il csp. Si può vedere che dalla cardinalità di 15 in poi si trova sempre una soluzione.
\vspace{1cm}

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.3]{immagini/graph_time-carddom.png}
\caption{Incremento della dimensione del dominio}
\label{fig: Incremento della dimensione del dominio}
\end{figure}

Prendendo in considerazione la densità del grafo, muovendoci nell'intervallo consentito (essendo un rapporto) [0,1] con incremento di 0.1 (figura \ref{fig: Incremento della densita del grafo}), notiamo che mediamente la \% di soluzioni rimane la stessa mentre il tempo calcolo aumenta; questo accade perché la tightness non cambia, ma essendoci più vincoli ci sono anche più combinazioni di valori che l'algoritmo deve considerare.
\vspace{1cm}

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.3]{immagini/graph_time-density.png}
\caption{Incremento della densità del grafo}
\label{fig: Incremento della densita del grafo}
\end{figure}
\vspace{1cm}

Nell'ultimo parametro, ovvero la strettezza (tighness) dei vincoli, abbiamo adottato lo stesso modus operandi utilizzato per la densità: incremento di 0.1 nell'intervallo [0,1] per quest'altra proporzione (figura \ref{fig: Incremento della strettezza dei vincoli}); segue un andamento calante sia per tempo di calcolo che per numero di csp risolvibili, con un picco verso il centro: questo perché all'aumentare della strettezza i csp risolvibili sono sempre meno e vengono individuati sempre più velocemente, mentre nell'intorno del valore 0.5 non è chiaro fino alla fine se sia risolvibile o meno; si fa notare che inizialmente il tempo di calcolo è comunque abbastanza alto  perché, sebbene le tuple permesse siano tante, nell'ac fuzzy vanno cercati supporti per tutti i valori dei domini e dunque il tempo richiesto è considerevole.
\vspace{1cm}
\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.3]{immagini/graph_time-tightness.png}
\caption{Incremento della strettezza dei vincoli}
\label{fig: Incremento della strettezza dei vincoli}
\end{figure}

\vspace{1cm}
\subsubsection{Sviluppi possibili}

Per come sono state modulate e integrate fra loro le varie componenti del progetto, è possibile ampliare la scelta degli algoritmi e metterli a confronto senza dover riscrivere parti di codice. L'interfaccia grafica è già predisposta alla generazione di csp generici (quindi non necessariamente fuzzy) ed è possibile aggiungere la scelta degli algoritmi da comparare aggiungendo le rispettive voci nel menù; nella classe GData è sufficiente aggiungere un vector che si occupi di tenere in memoria i dati di ogni algoritmo coinvolto e nella funzione $start$ della GUI un semplice controllo se l'algoritmo corrispondente è stato selezionato o meno dal menù. La classe wGraph richiederebbe un paio di ritocchi per gestire più risultati contemporaneamente (perlopiù per la scelta dei colori) ma in tal caso sarebbe interessante inserire un piccolo menù per la selezione/deselezione degli algoritmi da visualizzare. Il tempo richiesto dipenderebbe, quindi, dall'implementazione dei nuovi algoritmi.

\newpage
\listoffigures

 \end{document}
